﻿// 1404. 蜗牛漫步.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//

#include <iostream>


/*

https://www.acwing.com/problem/content/1406/
蜗牛莎莉喜欢在一个 N×N 的方格矩阵中散步。

她每次都从左上角出发。

方格矩阵中有空地（用 “.” 表示）和障碍（用 “#” 表示）。

下面是一个具体示例：


          A B C D E F G H
        1 S . . . . . # .
        2 . . . . # . . .
        3 . . . . . . . .
        4 . . . . . . . .
        5 . . . . . # . .
        6 # . . . . . . .
        7 . . . . . . . .
        8 . . . . . . . .
莎莉只能沿着水平或垂直方向移动。

在开始时，她位于 A1 位置，并选择一个方向（向下或向右）开始移动。

她会一直沿着一个方向移动，直到遇到矩阵边缘或障碍。

这时，她将转向 90 度，继续前进。

她在移动过程中，不能走出矩阵，或走进有障碍的格子中，也不能走到之前走过的格子中。

当她无法进行任何移动时，行动结束。

以下是上述示例中莎莉的一种行走情况：

          A B C D E F G H
        1 S---------+ # .
        2 . . . . # | . .
        3 . . . . . | . .
        4 . . . . . +---+
        5 . . . . . # . |
        6 # . . . . . . |
        7 +-----------+ |
        8 +-------------+
莎莉沿着右，下，右，下，左，上，右的方向走到了 G7 的位置，此时她无法进行任何移动，行动停止。
（前方是她走过的格子，不能进入，并且由于前方不是障碍且没有出界所以也不能转向）

给定具体的方格矩阵，请你帮莎莉找到一个最合理的行进路线，使得她可以经过的格子数量尽可能大。

输出可经过格子最大数量。

输入格式
第一行包含两个整数 N 和 B，分别表示矩阵尺寸以及障碍的数量。

接下来 B 行，每行描述一个障碍的具体位置，用如题面所示的字母和数字表示。

注意，当 N>26 时，输入中不会在 Z 列右侧设计障碍。

输出格式
输出一个整数，表示可经过格子的最大数量。

数据范围
1<N≤120
输入样例：
8 4
E2
A6
G1
F5
输出样例：
33
样例解释
一种最佳行进方式如下：

          A B C D E F G H
        1 S . . . . . # .
        2 | . . . # . . .
        3 | . . . +-----+
        4 | . . . | . . |
        5 +-------+ # . |
        6 # . . . . . . |
        7 +------------ |
        8 +-------------+
*/
int main()
{
    std::cout << "Hello World!\n";
}

 